Transport networks are wide area networks that provide connectivity for aggregated traffic streams. Modern transport networks increasingly employ wavelength division multiplexing (WDM) technology to utilize the vast transmission bandwidth of optical fiber. WDM is based on transmission of data over separate wavelength channels on each fiber. Presently, WDM is mainly employed as a point-to-point transmission technology. In such networks, optical signals on each wavelength are converted to electrical signals at each network node. On the other hand, WDM optical networking technology, which has been developed within the last decade, and which is becoming commercially available employs wavelengths on an end-to-end basis, without electrical conversion in the network. See, for example, Alexander, S. B., et al, "A precompetitive consortium on wide-band all-optical networks," J. of Lightwave Tech., Vol. 11, pp714-735, May, 1993; Chang, G. K., et al, "Multiwavelength reconfigurable WDM/ATM/SONET network testbed," J. of Lightwave Tech., vol. 14, pp. 1320-1340, June, 1996; Wagner, R. E., et al, "MONET: Multiwavelength optical networking," IEEE J. of Lightwave Tech., Vol. 14, pp. 1349-1355, June, 1996.
Provisioning of a transport network refers to assigning network resources to a static traffic demand. Efficient provisioning is essential in minimizing the investment made on the network required to accommodate a given demand. In the context of WDM optical networks, provisioning means routing and wavelength selection for a set of end-to-end wavelength allocation demands, given a demand distribution and a network topology. Provisioning of WDM networks has been subject to considerable interest, concentrating primarily on two context categories. The first of these treats the case of limited deployed fiber, where provisioning seeks to minimize the number of required wavelengths. Such applications are described, e.g., in Chlamtac, I., A. Ganz, and G. Karmi, "Lightpath communications: An approach to high bandwidth optical WAN's," IEEE Transactions on Communications, Vol. 40, No. 7, pp. 1171-1182, July, 1992, and Nagatsu, N., Y. Hamazumi, and K. Sato, "Electronics and Communications in Japan," Part 1,Vol. 78, No. 9, pp. 1-11, Sept. 1995. The second case that has been treated in the prior art is that involving a limited number of wavelengths per fiber, where provisioning seeks to minimize the amount of required fiber. See, for example, Nagatsu, N., and K. Sato, "Optical path accommodation design enabling cross-connect system scale evaluation," IEICE Trans. Commun., Vol. E78-B, No. 9, pp. 1339-1343, Sept., 1995; and Jeong, G. and E. Ayanoglu, "Comparison of wavelength-interchanging and wavelength-selective cross-connects in multiwavelength all-optical networks," Proc. IEEE INFOCOM '96, pp. 156-163, March, 1996.
FIG. 1 shows a typical network 100 to which provisioning methods may be applied. There, a set of nodes is interconnected by a plurality of fiber links to form a network. It is assumed that each connection between any two nodes (not necessarily adjacent) requires a dedicated wavelength on each link of its path. The typical context assumes that there is a fixed set of wavelengths available on each fiber, and therefore the connections are established at the expense of possibly multiple fibers on network links. Each fiber has a cost reflecting the installed fiber material, optical amplifiers, and optical termination equipment at both ends of the link. The objective of provisioning is taken as the minimization of the total network cost. Most prior attempts at provisioning for networks of the type exemplified by the network of FIG. 1 have sought an optimal solution prescribing how such provisioning should be accomplished.
A first class of prior provisioning solutions is applied in networks that do not account for possible network failures. Such networks are called primary networks; the objective in primary-network design is to minimize the cost associated with the working fibers. This problem has typically been formulated as an integer linear program (ILP) in a straightforward manner. However, the computational complexity of such ILP solutions has proven to be prohibitive for a network whose size is not trivial.
Moreover, since transport networks are intended to carry high volumes of traffic, network failures can have severe consequences. This imposes fault-tolerance as an important feature for provisioning practical transport networks. Fault-tolerance refers to the ability of the network to reconfigure and reestablish communication upon failure, and is widely known as restoration. Restoration entails rerouting connections around failed components under a targeted time-to-restore. A network with restoration capability requires redundant capacity to be used in the case of failures. An important concern in designing and provisioning such networks is to provide robustness with minimal redundancy.
While design methods devised for conventional, single-wavelength restorable networks can be employed in WDM optical networks, such prior designs typically prescribe switching all wavelengths in a fiber together in the case of failure. WDM optical networking, however, provides the capability to switch individual wavelengths, thereby offering a richer set of design methods. Some attempts at employing this flexibility have been treated, for example, in Nagatsu, N., S. Okamoto, and K. Sato, "Optical path cross-connect scale evaluation using path accommodation design for restricted wavelength multiplexing," IEEE JSAC, Vol. 14, No. 5, pp. 893-901, June, 1996; Sato, K. and N. Nagatsu, "Failure restoration in photonic transport networks using optical paths," Proc. of OFC '96, pp. 215-216, March, 1996; and Wuttisittikuikij, L., and M. J. O'Mahony, "Use of spare wavelengths for traffic restoration in multi-wavelength transport network," Proc. of ICC '95, PP. 1779-1792, June, 1992.
Solutions for provisioning WDM networks with restoration have, nevertheless, proven complex and time consuming.